1. Field of the Invention
The present invention relates to a method and system for caching data and, in particular, for using multiple data structures to manage data stored in cache.
2. Description of the Related Art
Data processing systems use a high-speed managed buffer memory, otherwise known as cache, to store frequently used data that is regularly maintained in a relatively slower memory device. For instance, a cache can be a RAM that buffers frequently used data regularly stored in a hard disk drive or a direct access storage device (DASD). After a track is read from the DASD, the track will be cached in RAM and available for subsequent data access requests (DARs). In this way, a storage controller processing read requests can avoid the mechanical delays of having to physically access and read data from the DASD. Cache can also be a high speed memory to a microprocessor to store data and instructions used by the microprocessor that are regularly maintained in RAM. Processor cache would buffer data from a volatile memory device, such as a DRAM or RAM.
Often data in cache is managed according to a least recently used (LRU) replacement algorithm in which the least recently used data is demoted from the cache to make room for new data. A first-in-first-out (FIFO) algorithm may also be used. The LRU replacement algorithm works by organizing the data in the cache in a linked list of data entries which is sorted according to the length of time since the most recent reference to each data entry. The most recently used (MRU) data is at one end of the linked list, while the least recently used (LRU) data is at the other. Data that is accessed from the linked list or added for the first time is promoted to the MRU end. When data is demoted to accommodate the addition of new data, the demoted data is removed from the LRU end.
Data can be accessed sequentially or non-sequentially. In the non-sequential access mode, data records are randomly requested. Such non-sequential accesses often occur when an application needs a particular record or data sets. Sequential data access occurs when numerous adjacent tracks are accessed, such as for a data backup operation or to generate a large report. For instance, a disk backup usually creates one long sequential reference to the entire disk, thus, flooding the cache with data. One problem with LRU schemes is that if a sequential data access floods the cache when placed at the MRU end, then other non-sequential records are demoted and removed from cache to accommodate the large sequential data access. Once the non-sequential data is demoted from cache, a data access request (DAR) for the demoted data must be handled by physically accessing the data from the slower memory device.
One goal of cache management algorithms is to maintain reasonable "hit ratios" for a given cache size. A "hit" is a DAR that was returned from cache, whereas a "miss" occurs when the requested data is not in cache and must be retrieved from DASD. A "hit ratio" is empirically determined from the number of hits divided by the total number of DARs, both hits and misses. System performance is often determined by the hit ratio. A system with a low hit ratio may cause delays to application program processing while requested data is retrieved from DASD.
A low hit ratio indicates that the data often was not in cache and had to be retrieved from DASD. Low hit ratios may occur if non-sequentially accessed data is "pushed" out of the cache to make room for a long series of sequentially accessed data. The higher probability of subsequent DARs toward non-sequentially accessed data further lowers the hit ratio because non-sequentially accessed data has a greater likelihood of being accessed. Moreover, the non-sequentially accessed data is "pushed out" of cache to make room for sequentially accessed data that has a lower likelihood of being accessed.
In certain systems, sequential data is placed at the LRU end and non-sequential data at the MRU end. Such methodologies often have the effect of providing an unreasonably low hit ratio for sequentially accessed data because the sequentially accessed data has some probability of being accessed (although usually less than non-sequentially accessed data). Algorithms that place sequentially accessed data at the LRU end cause the sequential data to be demoted very quickly, thus providing a relatively low hit ratio. Still further, if there is a continued sequence of write operations, i.e., modified data, read data could be pushed off the LRU list in cache, thus lowering the hit ratio for read accessed data.
In current storage controller systems, a battery backed up RAM or non-volatile storage unit (NVS) may maintain a shadow copy of all modified data in cache. Storage systems provided by International Business Machines Corporation ("IBM") include two write operations, a cache fast write (CFW) and a DASD fast write (DFW). In a DASD fast write operation, data is written to both the cache and the NVS unit. The DASD fast write operation allows fast write hits by maintaining two copies of all data modifications, one in cache and another in NVS storage. The non-volatile storage protects against data loss by saving the data for up to 48 hours (assuming a fully-charged battery) if power fails. When power is restored, then the data may be destaged from the NVS unit to DASD. DASD fast write applies to all write hits and to predictable writes. A write hit occurs when the requested data is in the cache.
Cache fast write (CFW) improves write operation performance for data that the user does not need to store on DASD. Because the data does not have to be stored on the DASD, cache fast write eliminates DASD access time for write hits and predictable write operations as the write data need only be stored in cache. Further, cache fast write does not use non-volatile storage. However, cache fast write data may be written to DASD during the execution of cache management algorithms. Aspects of the DASD fast write and cache fast write operations are described in IBM publication entitled "Storage Subsystem Library: IBM 3990 Storage Control Reference (Models 1, 2, and 3)", IBM document no. GA32-0099-06, (IBM Copyright 1988, 1994), which publication is incorporated herein by reference in its entirety.
When the NVS unit reaches a predetermined threshold, data in the NVS unit must be destaged from the NVS. In current systems, the entire LRU linked list including all data entries must be scanned to locate the least recently used DASD fast write data to select as a candidate for destaging from the NVS unit.
Moreover, with current systems, frequently updated data will not be destaged to disk because when the data is updated, a new time stamp is provided which places the modified data at the top of the LRU list. Thus, frequently modified data may be more susceptible to loss as a result of system failures because such data tends not to be destaged and is instead systematically placed at the MRU end of the linked list.